import java.util.HashSet;

/**
 * 268. 丢失的数字
 * https://leetcode.cn/problems/missing-number/description/
 */
class Solution {
    //异或运算
    public int missingNumber1(int[] nums) {
        int n = nums.length;
        int ret = 0;
        for(int i = 0; i < n; i++) {
            ret ^= i ^ nums[i];
        }
        ret ^= n;
        return ret;
    }
    //哈希表
    public int missingNumber2(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        int n = nums.length;
        for(int i = 0; i < n; i++) {
            set.add(nums[i]);
        }
        for(int i = 0; i <= n; i++) {
            if(!set.contains(i)) return i;
        }
        return -1;
    }
    //高斯求和公式
    public int missingNumber(int[] nums) {
        int n = nums.length;
        //0~n的和
        int sum = 0;
        for(int i = 0; i <= n; i++) {
            sum += i;
        }
        //数组元素之和
        int sumNums = 0;
        for(int i = 0; i < n; i++) {
            sumNums += nums[i];
        }
        return sum - sumNums;
    }
}